package design;

import java.util.Arrays;

public class leetCode204_countPrimes {
    public int countPrimes(int n) {
        if(n < 2) return 0;
        int[] arr = new int[n];
        Arrays.fill(arr,1);
        int ans = 0;
        for (int i = 3; i < arr.length; i++) {
            if(arr[i] == 1){
                ans++;
                for (int j = 2; i * j <= n ; j++) {
                    arr[j * i] = 2;
                }
            }
        }
        return ans;
    }

}
